package pers.vic.basics.leetcode;

import java.time.chrono.MinguoChronology;
import java.util.Arrays;

/**
 * @description: 64. 最小路径和 {@literal https://leetcode-cn.com/problems/minimum-path-sum/}
 * @author Vic.xu
 * @date: 2020/12/25 0025 9:43
 */
public class J0064_M_MinPathSum {

    /*
    给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
    说明：每次只能向下或者向右移动一步。
     */

    /**
     * 典型的动态规划
     */
    public static int minPathSum(int[][] grid) {
        int row = grid.length;
        int column = grid[0].length;
        int[][] dp = new int[row][column];
        dp[0][0] = grid[0][0];
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < column; j++) {
                if (i == 0 && j != 0) {
                    dp[0][j] = dp[0][j - 1] + grid[i][j];
                } else if (i != 0 && j == 0) {
                    dp[i][0] = dp[i - 1][0] + grid[i][j];
                } else if (i != 0 && j != 0) {
                    dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
                }
            }
        }
        return dp[row - 1][column - 1];
    }

    /**
     * 尝试下递归
     *
     * @param grid
     * @return
     */
    public static int minPathSum2(int[][] grid) {
        int row = grid.length;
        int column = grid[0].length;
        return min(grid, row - 1, column - 1);
    }

    public static int min(int[][] grid, int rowIndex, int columnIndex) {
        if (rowIndex == 0 && columnIndex == 0) {
            return grid[0][0];
        }
        if (rowIndex == 0) {
            return min(grid, 0, columnIndex - 1) + grid[rowIndex][columnIndex];
        }
        if (columnIndex == 0) {
            return min(grid, rowIndex - 1, 0) + grid[rowIndex][columnIndex];
        }
        return Math.min(min(grid, rowIndex - 1, columnIndex),min(grid, rowIndex, columnIndex-1)) + grid[rowIndex][columnIndex];
    }

    public static void main(String[] args) {
        int[][] grid = {{1, 2, 3}, {4,5,6}};
        System.out.println(minPathSum2(grid));


    }
}
